#pragma  once;
#include "../util/util.h"

namespace soy {

/// Divide an interval into multiple partitions.
/// Useful for breaking a document down into sections such as lines.
/// A 0 length interval has a single 0 length partition, numbered 0
/// If interval not 0 length then each partition non-zero length
/// When needed, positions after the interval are considered part of the last partition
/// but the end of the last partition can be found with PositionFromPartition(last+1).

class Partitioning {
private:
	// To avoid calculating all the partition positions whenever any text is inserted
	// there may be a step somewhere in the list.
	int stepPartition;
	int stepLength;
	SplitVector<int>* body;

	// Move step forward
	void ApplyStep( int partitionUpTo ) {
		if ( stepLength != 0 ) {
			body->RangeAddDelta( stepPartition + 1, partitionUpTo + 1, stepLength );
		}
		stepPartition = partitionUpTo;
		if ( stepPartition >= body->Length() - 1 ) {
			stepPartition = body->Length() - 1;
			stepLength = 0;
		}
	}

	// Move step backward
	void BackStep( int partitionDownTo ) {
		if ( stepLength != 0 ) {
			body->RangeAddDelta( partitionDownTo + 1, stepPartition + 1, -stepLength );
		}
		stepPartition = partitionDownTo;
	}

	void Allocate( int growSize ) {
		body = new SplitVector<int>( growSize );
		stepPartition = 0;
		stepLength = 0;
		body->Insert( 0, 0 );	// This value stays 0 for ever
		body->Insert( 1, 0 );	// This is the end of the first partition and will be the start of the second
	}

public:
	Partitioning( int growSize ) {
		Allocate( growSize );
	}

	~Partitioning() {
		delete body;
		body = 0;
	}

	int Partitions() const {
		return body->Length() - 1;
	}

	void InsertValue( int partition, int pos ) {
		if ( stepPartition < partition ) {
			ApplyStep( partition );
		}
		body->Insert( partition, pos );
		stepPartition++;
	}

	void SetValue( int partition, int pos ) {
		ApplyStep( partition + 1 );
		if ( ( partition < 0 ) || ( partition > body->Length() ) ) {
			return;
		}
		body->SetValueAt( partition, pos );
	}

	void OnInsertText( int partitionInsert, int delta ) {
		// Point all the partitions after the insertion point further along in the buffer
		if ( stepLength != 0 ) {
			if ( partitionInsert >= stepPartition ) {
				// Fill in up to the new insertion point
				ApplyStep( partitionInsert );
				stepLength += delta;
			} else if ( partitionInsert >= ( stepPartition - body->Length() / 10 ) ) {
				// Close to step but before so move step back
				BackStep( partitionInsert );
				stepLength += delta;
			} else {
				ApplyStep( body->Length() - 1 );
				stepPartition = partitionInsert;
				stepLength = delta;
			}
		} else {
			stepPartition = partitionInsert;
			stepLength = delta;
		}
	}

	void RemoveValue( int partition ) {
		if ( partition > stepPartition ) {
			ApplyStep( partition );
			stepPartition--;
		} else {
			stepPartition--;
		}
		body->Delete( partition );
	}

	int GetValue( int partition ) const {
		assert( partition >= 0 );
		assert( partition < body->Length() );
		if ( ( partition < 0 ) || ( partition >= body->Length() ) ) {
			return 0;
		}
		int pos = body->ValueAt( partition );
		if ( partition > stepPartition ) {
			pos += stepLength;
		}
		return pos;
	}

	/// Return value in range [0 .. Partitions() - 1] even for arguments outside interval
	int IndexOf( int pos ) const {
		if ( body->Length() <= 1 ) {
			return 0;
		}
		if ( pos >= ( GetValue( body->Length() - 1 ) ) ) {
			return body->Length() - 1 - 1;
		}
		int lower = 0;
		int upper = body->Length() - 1;
		do {
			int middle = ( upper + lower + 1 ) / 2; 	// Round high
			int posMiddle = body->ValueAt( middle );
			if ( middle > stepPartition ) {
				posMiddle += stepLength;
			}
			if ( pos < posMiddle ) {
				upper = middle - 1;
			} else {
				lower = middle;
			}
		} while ( lower < upper );
		return lower;
	}

	void DeleteAll() {
		int growSize = body->GetGrowSize();
		delete body;
		Allocate( growSize );
	}
};


};
